//给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。 
//
// 你可以假设数组中无重复元素。 
//
// 示例 1: 
//
// 输入: [1,3,5,6], 5
//输出: 2
// 
//
// 示例 2: 
//
// 输入: [1,3,5,6], 2
//输出: 1
// 
//
// 示例 3: 
//
// 输入: [1,3,5,6], 7
//输出: 4
// 
//
// 示例 4: 
//
// 输入: [1,3,5,6], 0
//输出: 0
// 
// Related Topics 数组 二分查找 
// 👍 946 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int binarySearch(int[] nums, int target){
        int head = 0, tail = nums.length-1, mid;
        while(tail - head > 3){
            mid = head + ((tail - head) >> 1);//注意这里的括号
            System.out.println("head:"+head+"\t,tail:"+tail+"\t,mid:"+mid);
            //00000001111111 第一个1
            if(nums[mid] >= target) tail = mid;
            else head = mid +1;
        }
        for(int i=head; i<=tail; i++){
            if( nums[i] >= target){
                return i;
            }
        }
        return -1;
    }
    public int searchInsert(int[] nums, int target) {
        //找到第一个大于等于目标值的index  000001111111
        int first_1 = binarySearch(nums, target);
        System.out.println("first_1:"+first_1);
        if(first_1 >= 0) {
            //如果存在first_1对应的值>=target
            //1. 如果相等：那么说明存在，返回first_1
            //2. 如果大于：说明不存在，需要插入，而插入的话，位置就是first_1这个位置
            return first_1;
        }else{
            //说明数组中不存在比target还大的，那么，说明需要将target加到数组最后一个位置+1的位置
            return nums.length;
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)
